# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head:return None

        def advance(head, n):
            while head and n>0:
                head = head.next
                n-=1
            return head

        def reverse(head):
            last = None
            while head:
                next = head.next
                head.next = last
                last = head
                head = next
            return last

        newHead = ListNode(None)
        newHead.next = head
        pre = advance(newHead, m-1)
        begin = pre.next
        end = advance(newHead, n)
        next = end.next
        pre.next = None
        end.next = None
        
        pre.next = reverse(begin)
        begin.next = next

        return newHead.next

head = ListNode(3)
head.next = ListNode(5)

Solution().reverseBetween(head, 1, 2)
